import java.io.InputStream;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 二分查找算法
 */
public class BinarySearch {

    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
/*        System.out.println("请输入数据：");
        for (int i = 0; i < numbers.length; i++)
        {
            numbers[i] = input.nextInt();
        }*/

      //  Scanner x=new Scanner(System.in);
        System.out.println("请输入数组场长度和数组");
     while(input.hasNext()) {
         int m = input.nextInt();
         //System.out.println(m);
         int[] numbers = new int[m];
         for (int i = 0; i < m; i++) {
             numbers[i] = input.nextInt();
         }
         System.out.println(Arrays.toString(numbers));
         System.out.println("请输入要定位的数值");
         int x = input.nextInt();
         System.out.println(x);
         int result = bSearch(numbers, x, numbers.length);

     }
    }

    //进行二分搜索
    public static int bSearch(int[] a, int x, int n) {
        int left = 0;
        int right = n - 1;
        int i = 0, j = 0;

        while (left <= right) {
            int middle = (left + right) / 2;
            if (x == a[middle]){
                i = j = middle;
                return middle;
            }
            if (x > a[middle])
                left = middle + 1;
            else
                right = middle - 1;
        }
        //i为x左边的元素,j为x右边的元素
        //这里i为right,j为left,是因为在上面算法中最后一次搜索的right和left交换了
        i = right;
        j = left;
        //x<a[0],说明数组中没有比x更小的元素了
        if(x<a[0]){
            System.out.println("比"+x+"大的最小数组元素的下标是"+j+", ");
            System.out.print("数组中不存在比"+x+"小的数组元素");
        }

        //x<a[8],说明数组中没有比x更大的元素了
        else if(x>a[a.length-1]){
            System.out.print("比"+x+"小的最大数组元素下标是"+i+", ");
            System.out.println("数组中不存在比"+x+"大的数组元素");
        }
        else{
            System.out.print("比"+x+"小的最大元素的下标为"+i+", ");
            System.out.println("比"+x+"大的最小元素下标为"+j);
            System.out.print("比"+x+"小的最大元素的下标为"+i+", ");
            System.out.println("比"+x+"大的最小元素下标为"+j);
            System.out.print("比"+x+"小的最大元素的下标为"+i+", ");
            System.out.println("比"+x+"大的最小元素下标为"+j);
            System.out.println("比"+x+"大的最小元素下标为"+j);
            System.out.println("DJXIN");
            System.out.println("DJXIN");
            System.out.println("DJXIN");System.out.println("DJXIN");
            System.out.println("DJXIN");
            System.out.println("DJXIN");
            System.out.println("DJXIN");
            System.out.println("DJXIN");



        }

        //未找到x,返回-1
        return -1;
    }

}

